package com.fs.leetcode.zifuchuan;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：hyq
 * @date ：Created in 2020/5/18 14:42
 * @description：
 * @modified By：
 */
public class lengthOfLongestSubstring {

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 思路：
     *    滑动窗口 使用hashmap维护滑动窗口保证窗口内的字符串无重复字符
     *    max = Math.max(max, i - left+1);
     *
     */
    public static int lengthOfLongestSubstring(String s) {

            if (s == null || s.length() == 0) {
                return 0;
            }
            // 初始化一堆遍历，默认使用第一个字符
            int begin = 0;
            int max = 1;
            Map<Character, Integer> characterIndexes = new HashMap<>();
            characterIndexes.put(s.charAt(0), 0);

            for (int i = 1; i < s.length(); i++) {
                Integer index = characterIndexes.get(s.charAt(i));
                // 已经存在
                if (index != null && index >= begin) {
                    begin = index + 1;
                } else {
                    max = Math.max(max, i - begin+1);
                }
                characterIndexes.put(s.charAt(i), i);
            }

            return max;
        }

    public static int lengthOfLongestSubstring2(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring2("abcabcbbae"));
    }


}
